﻿<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3c.org/TR/1999/REC-html401-19991224/loose.dtd">
<!-- saved from url=(0040)http://en.wikipedia.org/wiki/Exact_cover -->
<HTML lang=en dir=ltr xml:lang="en" 
xmlns="http://www.w3.org/1999/xhtml"><HEAD><TITLE>Exact cover - Wikipedia, the free encyclopedia</TITLE>
<META http-equiv=Content-Type content="text/html; charset=utf-8">
<META http-equiv=Content-Style-Type content=text/css>
<META content="MSHTML 6.00.2900.5897" name=GENERATOR><LINK 
title="Edit this page" href="/w/index.php?title=Exact_cover&amp;action=edit" 
type=application/x-wiki rel=alternate><LINK title="Edit this page" 
href="/w/index.php?title=Exact_cover&amp;action=edit" rel=edit><LINK 
href="Exact cover - Wikipedia, the free encyclopedia.files/combined.min.css" 
type=text/css rel=stylesheet><LINK 
href="Exact cover - Wikipedia, the free encyclopedia.files/jquery-ui-1.7.2.css" 
type=text/css rel=stylesheet><LINK 
href="http://en.wikipedia.org/apple-touch-icon.png" rel=apple-touch-icon><LINK 
href="/favicon.ico" rel="shortcut icon"><LINK title="Wikipedia (en)" 
href="/w/opensearch_desc.php" type=application/opensearchdescription+xml 
rel=search><LINK href="http://creativecommons.org/licenses/by-sa/3.0/" 
rel=copyright><LINK title="Wikipedia RSS Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=rss" 
type=application/rss+xml rel=alternate><LINK title="Wikipedia Atom Feed" 
href="/w/index.php?title=Special:RecentChanges&amp;feed=atom" 
type=application/atom+xml rel=alternate><LINK media=screen 
href="Exact cover - Wikipedia, the free encyclopedia.files/shared.css" 
type=text/css rel=stylesheet><LINK media=print 
href="Exact cover - Wikipedia, the free encyclopedia.files/commonPrint.css" 
type=text/css rel=stylesheet><LINK media=screen 
href="Exact cover - Wikipedia, the free encyclopedia.files/main.css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Exact cover - Wikipedia, the free encyclopedia.files\main(1).css" 
type=text/css rel=stylesheet><!--[if lt IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE50Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><!--[if IE 5.5000]><link rel="stylesheet" href="/skins-1.5/monobook/IE55Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><!--[if IE 6]><LINK 
media=screen 
href="Exact cover - Wikipedia, the free encyclopedia.files/IE60Fixes.css" 
type=text/css rel=stylesheet><![endif]--><!--[if IE 7]><link rel="stylesheet" href="/skins-1.5/monobook/IE70Fixes.css?257z2" type="text/css" media="screen" /><![endif]--><LINK 
media=all href="Exact cover - Wikipedia, the free encyclopedia.files/index.css" 
type=text/css rel=stylesheet><LINK media=print 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Exact cover - Wikipedia, the free encyclopedia.files\index(1).css" 
type=text/css rel=stylesheet><LINK media=handheld 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Exact cover - Wikipedia, the free encyclopedia.files\index(2).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Exact cover - Wikipedia, the free encyclopedia.files\index(3).css" 
type=text/css rel=stylesheet><LINK media=all 
href="G:\l论文资料\基于WPF的数独游戏的开发\百科\数独资料\Exact cover - Wikipedia, the free encyclopedia.files\index(4).css" 
type=text/css rel=stylesheet>
<SCRIPT type=text/javascript>
var skin="monobook",
stylepath="/skins-1.5",
wgArticlePath="/wiki/$1",
wgScriptPath="/w",
wgScriptExtension=".php",
wgScript="/w/index.php",
wgVariantArticlePath=false,
wgActionPaths={},
wgServer="http://en.wikipedia.org",
wgCanonicalNamespace="",
wgCanonicalSpecialPageName=false,
wgNamespaceNumber=0,
wgPageName="Exact_cover",
wgTitle="Exact cover",
wgAction="view",
wgArticleId=2828651,
wgIsArticle=true,
wgUserName=null,
wgUserGroups=null,
wgUserLanguage="en",
wgContentLanguage="en",
wgBreakFrames=false,
wgCurRevisionId=325680852,
wgVersion="1.16alpha-wmf",
wgEnableAPI=true,
wgEnableWriteAPI=true,
wgSeparatorTransformTable=["", ""],
wgDigitTransformTable=["", ""],
wgMainPageTitle="Main Page",
wgFormattedNamespaces={"-2": "Media", "-1": "Special", "0": "", "1": "Talk", "2": "User", "3": "User talk", "4": "Wikipedia", "5": "Wikipedia talk", "6": "File", "7": "File talk", "8": "MediaWiki", "9": "MediaWiki talk", "10": "Template", "11": "Template talk", "12": "Help", "13": "Help talk", "14": "Category", "15": "Category talk", "100": "Portal", "101": "Portal talk"},
wgNamespaceIds={"media": -2, "special": -1, "": 0, "talk": 1, "user": 2, "user_talk": 3, "wikipedia": 4, "wikipedia_talk": 5, "file": 6, "file_talk": 7, "mediawiki": 8, "mediawiki_talk": 9, "template": 10, "template_talk": 11, "help": 12, "help_talk": 13, "category": 14, "category_talk": 15, "portal": 100, "portal_talk": 101, "wp": 4, "wt": 5, "image": 6, "image_talk": 7},
wgMWSuggestTemplate="http://en.wikipedia.org/w/api.php?action=opensearch\x26search={searchTerms}\x26namespace={namespaces}\x26suggest",
wgDBname="enwiki",
wgSearchNamespaces=[0],
wgMWSuggestMessages=["with suggestions", "no suggestions"],
wgRestrictionEdit=[],
wgRestrictionMove=[],
wgTrackingToken="ca24b9c0b660b072ba7be1b510a87114",
wgClickTrackingIsThrottled=true,
wgNotice="",
wgNoticeLocal="";
</SCRIPT>

<SCRIPT src="Exact cover - Wikipedia, the free encyclopedia.files/wikibits.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="Exact cover - Wikipedia, the free encyclopedia.files/ajax.js" 
type=text/javascript></SCRIPT>

<SCRIPT src="Exact cover - Wikipedia, the free encyclopedia.files/mwsuggest.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Exact cover - Wikipedia, the free encyclopedia.files/js2.combined.min.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Exact cover - Wikipedia, the free encyclopedia.files/plugins.combined.min.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Exact cover - Wikipedia, the free encyclopedia.files/CollapsibleTabs.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Exact cover - Wikipedia, the free encyclopedia.files/ClickTracking.js" 
type=text/javascript></SCRIPT>

<SCRIPT 
src="Exact cover - Wikipedia, the free encyclopedia.files/centralnotice.js" 
type=text/javascript></SCRIPT>
<!--[if lt IE 7]>
<SCRIPT src="Exact cover - Wikipedia, the free encyclopedia.files/IEFixes.js" 
type=text/javascript></SCRIPT>

<META http-equiv=imagetoolbar content=no><![endif]-->
<SCRIPT src="Exact cover - Wikipedia, the free encyclopedia.files/index.php" 
type=text/javascript></SCRIPT>
</HEAD>
<BODY class="mediawiki ltr ns-0 ns-subject page-Exact_cover skin-monobook">
<DIV id=globalWrapper>
<DIV id=column-content>
<DIV id=content><A id=top></A>
<DIV id=siteNotice>
<SCRIPT 
type=text/javascript>if (wgNotice != '') document.writeln(wgNotice);</SCRIPT>
</DIV>
<H1 class=firstHeading id=firstHeading>Exact cover</H1>
<DIV id=bodyContent>
<H3 id=siteSub>From Wikipedia, the free encyclopedia</H3>
<DIV id=contentSub></DIV>
<DIV id=jump-to-nav>Jump to: <A 
href="http://en.wikipedia.org/wiki/Exact_cover#column-one">navigation</A>, <A 
href="http://en.wikipedia.org/wiki/Exact_cover#searchInput">search</A></DIV><!-- start content -->
<P>In <A title=Mathematics 
href="http://en.wikipedia.org/wiki/Mathematics">mathematics</A>, given a 
collection <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of <A title=Subset href="http://en.wikipedia.org/wiki/Subset">subsets</A> of a 
set <I>X</I>, an <B>exact cover</B> is a subcollection <IMG class=tex 
alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
such that each element in <I>X</I> is contained in <I>exactly one</I> subset in 
<IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">. 
One says that each element in <I>X</I> <B>is covered by</B> exactly one subset 
in <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">. 
An exact cover is a kind of <A title="Cover (topology)" 
href="http://en.wikipedia.org/wiki/Cover_(topology)">cover</A>.</P>
<P>In <A title="Computer science" 
href="http://en.wikipedia.org/wiki/Computer_science">computer science</A>, the 
<B>exact cover problem</B> is a <A title="Decision problem" 
href="http://en.wikipedia.org/wiki/Decision_problem">decision problem</A> to 
find an exact cover or else determine none exists. The exact cover problem is <A 
title=NP-complete 
href="http://en.wikipedia.org/wiki/NP-complete">NP-complete</A><SUP 
class=reference id=cite_ref-0><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-0"><SPAN>[</SPAN>1<SPAN>]</SPAN></A></SUP> 
and is one of <A title="Karp's 21 NP-complete problems" 
href="http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems">Karp's 21 
NP-complete problems</A>.<SUP class=reference id=cite_ref-1><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-1"><SPAN>[</SPAN>2<SPAN>]</SPAN></A></SUP> 
The exact cover problem is a kind of <A title="Constraint satisfaction problem" 
href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem">constraint 
satisfaction problem</A>.</P>
<P>An exact cover problem can be represented by an <A title="Incidence matrix" 
href="http://en.wikipedia.org/wiki/Incidence_matrix">incidence matrix</A> or a 
<A title="Bipartite graph" 
href="http://en.wikipedia.org/wiki/Bipartite_graph">bipartite graph</A>.</P>
<P><A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Knuth's Algorithm X</A> 
is an <A title=Algorithm 
href="http://en.wikipedia.org/wiki/Algorithm">algorithm</A> that finds all 
solutions to an exact cover problem. <A title="Dancing Links" 
href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A>, commonly 
known as DLX, is the technique suggested by <A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</A> to efficiently 
implement his Algorithm X on a computer.</P>
<P>The standard exact cover problem can be generalized slightly to involve not 
only "exactly-one" constraints but also "at-most-one" constraints.</P>
<P>Finding <A title=Pentomino 
href="http://en.wikipedia.org/wiki/Pentomino">Pentomino</A> tilings and solving 
<A title=Sudoku href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</A> are 
noteworthy examples of exact cover problems. The <A class=mw-redirect 
title="N queens problem" href="http://en.wikipedia.org/wiki/N_queens_problem">N 
queens problem</A> is a slightly generalized exact cover problem.</P>
<TABLE class=toc id=toc>
  <TBODY>
  <TR>
    <TD>
      <DIV id=toctitle>
      <H2>Contents</H2></DIV>
      <UL>
        <LI class="toclevel-1 tocsection-1"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Formal_definition"><SPAN 
        class=tocnumber>1</SPAN> <SPAN class=toctext>Formal 
        definition</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-2"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Basic_examples"><SPAN 
          class=tocnumber>1.1</SPAN> <SPAN class=toctext>Basic 
          examples</SPAN></A> 
          <LI class="toclevel-2 tocsection-3"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example"><SPAN 
          class=tocnumber>1.2</SPAN> <SPAN class=toctext>Detailed 
          example</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-4"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Representations"><SPAN 
        class=tocnumber>2</SPAN> <SPAN class=toctext>Representations</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-5"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Standard_representation"><SPAN 
          class=tocnumber>2.1</SPAN> <SPAN class=toctext>Standard 
          representation</SPAN></A> 
          <LI class="toclevel-2 tocsection-6"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Inverse_representation"><SPAN 
          class=tocnumber>2.2</SPAN> <SPAN class=toctext>Inverse 
          representation</SPAN></A> 
          <LI class="toclevel-2 tocsection-7"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Matrix_and_hypergraph_representations"><SPAN 
          class=tocnumber>2.3</SPAN> <SPAN class=toctext>Matrix and hypergraph 
          representations</SPAN></A> 
          <LI class="toclevel-2 tocsection-8"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Graph_representation"><SPAN 
          class=tocnumber>2.4</SPAN> <SPAN class=toctext>Graph 
          representation</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-9"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems"><SPAN 
        class=tocnumber>3</SPAN> <SPAN class=toctext>Equivalent 
        problems</SPAN></A> 
        <LI class="toclevel-1 tocsection-10"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set"><SPAN 
        class=tocnumber>4</SPAN> <SPAN class=toctext>Exact hitting 
        set</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-11"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set_example"><SPAN 
          class=tocnumber>4.1</SPAN> <SPAN class=toctext>Exact hitting set 
          example</SPAN></A> 
          <LI class="toclevel-2 tocsection-12"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Dual_example"><SPAN 
          class=tocnumber>4.2</SPAN> <SPAN class=toctext>Dual example</SPAN></A> 
          </LI></UL>
        <LI class="toclevel-1 tocsection-13"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Finding_solutions"><SPAN 
        class=tocnumber>5</SPAN> <SPAN class=toctext>Finding 
        solutions</SPAN></A> 
        <LI class="toclevel-1 tocsection-14"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Generalizations"><SPAN 
        class=tocnumber>6</SPAN> <SPAN class=toctext>Generalizations</SPAN></A> 
        <LI class="toclevel-1 tocsection-15"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#Noteworthy_examples"><SPAN 
        class=tocnumber>7</SPAN> <SPAN class=toctext>Noteworthy 
        examples</SPAN></A> 
        <UL>
          <LI class="toclevel-2 tocsection-16"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Pentomino_tiling"><SPAN 
          class=tocnumber>7.1</SPAN> <SPAN class=toctext>Pentomino 
          tiling</SPAN></A> 
          <LI class="toclevel-2 tocsection-17"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#Sudoku"><SPAN 
          class=tocnumber>7.2</SPAN> <SPAN class=toctext>Sudoku</SPAN></A> 
          <LI class="toclevel-2 tocsection-18"><A 
          href="http://en.wikipedia.org/wiki/Exact_cover#N_queens_problem"><SPAN 
          class=tocnumber>7.3</SPAN> <SPAN class=toctext>N queens 
          problem</SPAN></A> </LI></UL>
        <LI class="toclevel-1 tocsection-19"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#See_also"><SPAN 
        class=tocnumber>8</SPAN> <SPAN class=toctext>See also</SPAN></A> 
        <LI class="toclevel-1 tocsection-20"><A 
        href="http://en.wikipedia.org/wiki/Exact_cover#References"><SPAN 
        class=tocnumber>9</SPAN> <SPAN class=toctext>References</SPAN></A> 
      </LI></UL></TD></TR></TBODY></TABLE>
<SCRIPT type=text/javascript>
//<![CDATA[
if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } 
//]]>
</SCRIPT>

<H2><SPAN class=editsection>[<A title="Edit section: Formal definition" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=1">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Formal_definition>Formal definition</SPAN></H2>
<P>Given a collection <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of <A title=Subset href="http://en.wikipedia.org/wiki/Subset">subsets</A> of a 
set <I>X</I>, an exact cover of <I>X</I> is a subcollection <IMG class=tex 
alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
that satisfies two conditions:</P>
<UL>
  <LI>The <A title="Intersection (set theory)" 
  href="http://en.wikipedia.org/wiki/Intersection_(set_theory)">intersection</A> 
  of any two distinct subsets in <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
  is <A title="Empty set" 
  href="http://en.wikipedia.org/wiki/Empty_set">empty</A>, i.e., the subsets in 
  <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
  are <A class=mw-redirect title="Pairwise disjoint" 
  href="http://en.wikipedia.org/wiki/Pairwise_disjoint">pairwise disjoint</A>. 
  In other words, each element in <I>X</I> is contained in <I>at most one</I> 
  subset in <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">. 

  <LI>The <A title="Union (set theory)" 
  href="http://en.wikipedia.org/wiki/Union_(set_theory)">union</A> of the 
  subsets in <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
  is <I>X</I>, i.e., the subsets in <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
  <A title="Cover (topology)" 
  href="http://en.wikipedia.org/wiki/Cover_(topology)">cover</A> <I>X</I>. In 
  other words, each element in <I>X</I> is contained in <I>at least one</I> 
  subset in <IMG class=tex alt=\mathcal{S}^* 
  src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">. 
  </LI></UL>
<P>In short, an exact cover is "exact" in the sense that each element in 
<I>X</I> is contained in <I>exactly one</I> subset in <IMG class=tex 
alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png">.</P>
<P>Equivalently, an exact cover of <I>X</I> is a subcollection <IMG class=tex 
alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
of <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
that <A title="Partition of a set" 
href="http://en.wikipedia.org/wiki/Partition_of_a_set">partitions</A> 
<I>X</I>.</P>
<P>For an exact cover of <I>X</I> to exist, it is necessary that:</P>
<UL>
  <LI>The union of the subsets in <IMG class=tex alt=\mathcal{S} 
  src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
  is <I>X</I>. In other words, each element in <I>X</I> is contained in at least 
  one subset in <IMG class=tex alt=\mathcal{S} 
  src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png">. 
  </LI></UL>
<P>If the <A title="Empty set" 
href="http://en.wikipedia.org/wiki/Empty_set">empty set</A> ∅ is contained in 
<IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png">, 
then it makes no difference whether or not it is in any exact cover. Thus it is 
typical to assume that:</P>
<UL>
  <LI>The empty set is not in <IMG class=tex alt=\mathcal{S} 
  src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png">. 
  In other words, each subset in <IMG class=tex alt=\mathcal{S} 
  src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
  contains at least one element. </LI></UL>
<H3><SPAN class=editsection>[<A title="Edit section: Basic examples" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=2">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Basic_examples>Basic examples</SPAN></H3>
<P>Let <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
= {<I>N</I>, <I>O</I>, <I>E</I>, <I>P</I>} be a collection of subsets of a set 
<I>X</I> = {1, 2, 3, 4} such that:</P>
<UL>
  <LI><I>N</I> = { }, 
  <LI><I>O</I> = {1, 3}, 
  <LI><I>E</I> = {2, 4}, and 
  <LI><I>P</I> = {2, 3}. </LI></UL>
<P>The subcollection {<I>O</I>, <I>E</I>} is an exact cover of <I>X</I>, since 
the subsets <I>O</I> = {1, 3} and <I>E</I> = {2, 4} are disjoint and their union 
is <I>X</I> = {1, 2, 3, 4}.</P>
<P>The subcollection {<I>N</I>, <I>O</I>, <I>E</I>} is also an exact cover of 
<I>X</I>. Including the empty set <I>N</I> = { } makes no difference, as it is 
disjoint with all subsets and does not change the union.</P>
<P>The subcollection {<I>E</I>, <I>P</I>} is not an exact cover of <I>X</I>. The 
intersection of the subsets <I>E</I> and <I>P</I>, {2}, is not empty: The 
subsets <I>E</I> and <I>P</I> are not disjoint. Moreover, the union of the 
subsets <I>E</I> and <I>P</I>, {2, 3, 4}, is not <I>X</I> = {1, 2, 3, 4}: 
Neither <I>E</I> nor <I>P</I> covers the element 1.</P>
<P>On the other hand, there is no exact cover—indeed, not even a <A title=Cover 
href="http://en.wikipedia.org/wiki/Cover">cover</A>—of <I>Y</I> = {1, 2, 3, 4, 
5} because <IMG class=tex alt="\bigcup \mathcal{S}" 
src="Exact cover - Wikipedia, the free encyclopedia.files/fca462c11bab3de6200c8fd19a5425b3.png"> 
= {1, 2, 3, 4} is a proper subset of <I>Y</I>: None of the subsets in <IMG 
class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
contains the element 5.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Detailed example" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=3">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Detailed_example>Detailed example</SPAN></H3>
<P>Let <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
= {<I>A</I>, <I>B</I>, <I>C</I>, <I>D</I>, <I>E</I>, <I>F</I>} be a collection 
of subsets of a set <I>X</I> = {1, 2, 3, 4, 5, 6, 7} such that:</P>
<UL>
  <LI><I>A</I> = {1, 4, 7}; 
  <LI><I>B</I> = {1, 4}; 
  <LI><I>C</I> = {4, 5, 7}; 
  <LI><I>D</I> = {3, 5, 6}; 
  <LI><I>E</I> = {2, 3, 6, 7}; and 
  <LI><I>F</I> = {2, 7}. </LI></UL>
<P>Then the subcollection <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} is an exact cover, since each element in 
<I>X</I> is contained in exactly one of the subsets:</P>
<UL>
  <LI><I>B</I> = {1, 4}; 
  <LI><I>D</I> = {3, 5, 6}; or 
  <LI><I>F</I> = {2, 7}. </LI></UL>
<P>Moreover, {<I>B</I>, <I>D</I>, <I>F</I>} is the only exact cover, as the 
following argument demonstrates: Because <I>A</I> and <I>B</I> are the only 
subsets containing 1, an exact cover must contain <I>A</I> or <I>B</I>, but not 
both. If an exact cover contains <I>A</I>, then it doesn't contain <I>B</I>, 
<I>C</I>, <I>E</I>, or <I>F</I>, as each of these subsets has an element in 
common with <I>A</I>. Then <I>D</I> is the only remaining subset, but the 
collection {<I>A</I>, <I>D</I>} doesn't cover the element 2. In conclusion, 
there is no exact cover containing <I>A</I>. On the other hand, if an exact 
cover contains <I>B</I>, then it doesn't contain <I>A</I> or <I>C</I>, as each 
of these subsets has an element in common with <I>B</I>. Because <I>D</I> is the 
only remaining subset containing 5, <I>D</I> must be part of the exact cover. If 
an exact cover contains <I>D</I>, then it doesn't contain <I>E</I>, as <I>E</I> 
has an element in common with <I>D</I>. Then <I>F</I> is the only remaining 
subset, and the collection {<I>B</I>, <I>D</I>, <I>F</I>} is indeed an exact 
cover. See the <A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X#Example">example</A> in 
the article on <A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Knuth's Algorithm X</A> 
for a matrix-based version of this argument.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Representations" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=4">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Representations>Representations</SPAN></H2>
<P>An exact cover problem is defined by the <A title="Binary relation" 
href="http://en.wikipedia.org/wiki/Binary_relation">binary relation</A> 
"contains" between subsets in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
and elements in <I>X</I>. There are different equivalent ways to represent this 
relation.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Standard representation" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=5">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Standard_representation>Standard 
representation</SPAN></H3>
<P>The standard way to represent the relation "contains" is to list the elements 
in each subset.</P>
<P>For example, the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed 
example</A> above uses this standard representation:</P>
<UL>
  <LI><I>A</I> = {1, 4, 7}; 
  <LI><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>B</I></SPAN> = {<SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">1</SPAN>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">4</SPAN>}; 
  <LI><I>C</I> = {4, 5, 7}; 
  <LI><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>D</I></SPAN> = {<SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">3</SPAN>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">5</SPAN>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">6</SPAN>}; 
  <LI><I>E</I> = {2, 3, 6, 7}; and 
  <LI><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>F</I></SPAN> = {<SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">2</SPAN>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">7</SPAN>}. </LI></UL>
<P>Again, the subcollection <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} is an exact cover, since each element is 
contained in exactly one selected subset, as the highlighting makes clear.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Inverse representation" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=6">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Inverse_representation>Inverse 
representation</SPAN></H3>
<P>The relation "contains" between subsets and elements can be <A 
title="Inverse relation" 
href="http://en.wikipedia.org/wiki/Inverse_relation">inverted</A>, listing the 
subsets each element is contained in.</P>
<P>For example, the relation "contains" in the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed 
example</A> above can be represented by listing the subsets each element is 
contained in:</P>
<UL>
  <LI>1 is contained in <I>A</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>B</I></SPAN>; 
  <LI>2 is contained in <I>E</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>F</I></SPAN>; 
  <LI>3 is contained in <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>D</I></SPAN>, <I>E</I>; 
  <LI>4 is contained in <I>A</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>B</I></SPAN>, <I>C</I>; 
  <LI>5 is contained in <I>C</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>D</I></SPAN>; 
  <LI>6 is contained in <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>D</I></SPAN>, <I>E</I>; and 
  <LI>7 is contained in <I>A</I>, <I>C</I>, <I>E</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>F</I></SPAN>. </LI></UL>
<P>Again, the subcollection <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} is an exact cover, since each element is 
contained in exactly one selected subset, as the highlighting makes clear.</P>
<P>When solving an exact cover problem, it is often useful to switch between the 
standard and inverse representations.</P>
<H3><SPAN class=editsection>[<A 
title="Edit section: Matrix and hypergraph representations" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=7">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Matrix_and_hypergraph_representations>Matrix and 
hypergraph representations</SPAN></H3>
<P>The relation "contains" can be represented by an <A title="Incidence matrix" 
href="http://en.wikipedia.org/wiki/Incidence_matrix">incidence matrix</A>.</P>
<P>The matrix includes one row for each subset in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
and one column for each element in <I>X</I>. The entry in a particular row and 
column is 1 if the corresponding subset contains the corresponding element, and 
is 0 otherwise. As each row represents the elements contained in the 
corresponding subset and each column represents the subsets containing the 
corresponding element, an incidence matrix effectively provides both the 
standard and inverse representations.</P>
<P>In the matrix representation, an exact cover is a selection of rows such that 
each column contains a 1 in exactly one selected row.</P>
<P>For example, the relation "contains" in the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed 
example</A> above can be represented by a 6×7 incidence matrix:<SUP 
class=reference id=cite_ref-2><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-2"><SPAN>[</SPAN>3<SPAN>]</SPAN></A></SUP></P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TH></TH>
      <TH>1</TH>
      <TH>2</TH>
      <TH>3</TH>
      <TH>4</TH>
      <TH>5</TH>
      <TH>6</TH>
      <TH>7</TH></TR>
    <TR>
      <TH><I>A</I></TH>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>B</I></SPAN></TH>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>C</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>D</I></SPAN></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>E</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>F</I></SPAN></TH>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR></TBODY></TABLE></DD></DL>
<P>Again, the subcollection <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} is an exact cover, since each element is 
contained in exactly one selected subset, i.e., each column contains a 1 in 
exactly one selected row, as the highlighting makes clear.</P>
<P>See the <A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X#Example">example</A> in 
the article on <A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Knuth's Algorithm X</A> 
for a matrix-based solution to the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed 
example</A> above.</P>
<P>In turn, the incidence matrix can be seen also as describing a <A 
title=Hypergraph href="http://en.wikipedia.org/wiki/Hypergraph">hypergraph</A>. 
The hypergraph includes one node for each element in <I>X</I> and one edge for 
each subset in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png">; 
each node is included in exactly one of the edges forming the cover.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Graph representation" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=8">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Graph_representation>Graph representation</SPAN></H3>
<P>The relation "contains" can be represented by a <A title="Bipartite graph" 
href="http://en.wikipedia.org/wiki/Bipartite_graph">bipartite graph</A>.</P>
<P>The vertices of the graph are divided into two disjoint sets, one 
representing the subsets in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
and another representing the elements in <I>X</I>. If a subset contains an 
element, an edge connects the corresponding vertices in the graph.</P>
<P>In the graph representation, an exact cover is a selection of vertices 
corresponding to subsets such that each vertex corresponding to an element is 
connected to exactly one selected vertex.</P>
<P>For example, the relation "contains" in the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed 
example</A> above can be represented by a bipartite graph with 6+7 = 13 
vertices:</P>
<DIV class=floatnone><A class=image 
href="http://en.wikipedia.org/wiki/File:Exact-cover-bigraph-highlighted.svg"><IMG 
height=300 alt=Exact-cover-bigraph-highlighted.svg 
src="Exact cover - Wikipedia, the free encyclopedia.files/300px-Exact-cover-bigraph-highlighted.svg.png" 
width=300></A></DIV>
<P>Again, the subcollection <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} is an exact cover, since each element is 
contained in exactly one selected subset, i.e., the vertex corresponding to each 
element in <I>X</I> is connected to exactly one selected vertex, as the 
highlighting makes clear.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Equivalent problems" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=9">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Equivalent_problems>Equivalent problems</SPAN></H2>
<P>Although the canonical exact cover problem involves a collection <IMG 
class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of a set <I>X</I>, the logic does not depend on the presence of 
subsets containing elements. An "abstract exact cover problem" arises whenever 
there is a <A title="Binary relation" 
href="http://en.wikipedia.org/wiki/Binary_relation">binary relation</A> between 
two sets <I>P</I> and <I>Q</I> and the goal is to select a subset <I>P*</I> of 
<I>P</I> such that each element in <I>Q</I> is related to <I>exactly one</I> 
element in <I>P*</I>. In general, the elements of <I>P</I> represent choices and 
the elements of <I>Q</I> represent "exactly-one" constraints on those 
choices.</P>
<P>More formally, given a binary relation <I>R</I> <IMG class=tex 
alt="\subseteq " 
src="Exact cover - Wikipedia, the free encyclopedia.files/a07903a0504f50f27e2a85c27e47fbd5.png"> 
<I>P</I> × <I>Q</I> between sets <I>P</I> and <I>Q</I>, one can call a subset 
<I>P*</I> of <I>P</I> an "abstract exact cover" of <I>Q</I> if each element in 
<I>Q</I> is <I>R</I> <SUP>-1</SUP>-related to exactly one element in <I>P*</I>. 
Here <I>R</I> <SUP>-1</SUP> is the <A title="Inverse relation" 
href="http://en.wikipedia.org/wiki/Inverse_relation">inverse</A> of 
<I>R</I>.</P>
<P>In general, <I>R</I> <SUP>-1</SUP> <A title="Restriction (mathematics)" 
href="http://en.wikipedia.org/wiki/Restriction_(mathematics)">restricted</A> to 
<I>Q</I> × <I>P*</I> is a <A title="Function (mathematics)" 
href="http://en.wikipedia.org/wiki/Function_(mathematics)">function</A> from 
<I>Q</I> to <I>P*</I>, which maps each element in <I>Q</I> to the unique element 
in <I>P*</I> that is <I>R</I>-related that element in <I>Q</I>. This function is 
<A class=mw-redirect title=Onto 
href="http://en.wikipedia.org/wiki/Onto">onto</A>, unless <I>P*</I> contains the 
"empty set," i.e., an element which isn't <I>R</I>-related to any element in 
<I>Q</I>.</P>
<P>In the canonical exact cover problem, <I>P</I> is a collection <IMG class=tex 
alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of <I>X</I>, <I>Q</I> is the set <I>X</I>, <I>R</I> is the binary 
relation "contains" between subsets and elements, and <I>R</I> <SUP>-1</SUP> 
restricted to <I>Q</I> × <I>P*</I> is the function "is contained in" from 
elements to selected subsets.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Exact hitting set" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=10">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Exact_hitting_set>Exact hitting set</SPAN></H2>
<P>In <A title=Mathematics 
href="http://en.wikipedia.org/wiki/Mathematics">mathematics</A>, given a 
collection <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of a set <I>X</I>, an <B>exact hitting set</B> <I>X*</I> is a subset 
of <I>X</I> such that each subset in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
contains <I>exactly one</I> element in <I>X*</I>. One says that each subset in 
<IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
<B>is hit by</B> exactly one element in <I>X*</I>.</P>
<P>In <A title="Computer science" 
href="http://en.wikipedia.org/wiki/Computer_science">computer science</A>, the 
<B>exact hitting set problem</B> is a <A title="Decision problem" 
href="http://en.wikipedia.org/wiki/Decision_problem">decision problem</A> to 
find an exact hitting set or else determine none exists.</P>
<P>The exact hitting set problem is an abstract exact cover problem. In the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems">notation 
above</A>, <I>P</I> is the set <I>X</I>, <I>Q</I> is a collection <IMG class=tex 
alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
of subsets of <I>X</I>, <I>R</I> is the binary relation "is contained in" 
between elements and subsets, and <I>R</I> <SUP>-1</SUP> restricted to <I>Q</I> 
× <I>P*</I> is the function "contains" from subsets to selected elements.</P>
<P>Whereas an exact cover problem involves selecting subsets and the relation 
"contains" from subsets to elements, an exact hitting set problem involves 
selecting elements and the relation "is contained in" from elements to subsets. 
In a sense, an exact hitting set problem is the inverse of the exact cover 
problem involving the same set and collection of subsets.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Exact hitting set example" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=11">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Exact_hitting_set_example>Exact hitting set 
example</SPAN></H3>
<P>As in the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed exact 
cover example</A> above, let <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
= {<I>A</I>, <I>B</I>, <I>C</I>, <I>D</I>, <I>E</I>, <I>F</I>} be a collection 
of subsets of a set <I>X</I> = {1, 2, 3, 4, 5, 6, 7} such that:</P>
<UL>
  <LI><I>A</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN>, 4, 7}; 
  <LI><I>B</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN>, 4}; 
  <LI><I>C</I> = {4, <SPAN style="FONT-WEIGHT: bold; COLOR: red">5</SPAN>, 7}; 
  <LI><I>D</I> = {3, <SPAN style="FONT-WEIGHT: bold; COLOR: red">5</SPAN>, 6}; 
  <LI><I>E</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red">2</SPAN>, 3, 6, 
  7}; and 
  <LI><I>F</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red">2</SPAN>, 7}. 
</LI></UL>
<P>Then <I>X*</I> = {1, 2, 5} is an exact hitting set, since each subset in <IMG 
class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
contains exactly one element in <I>X*</I>, as the highlighting makes clear.</P>
<P>Moreover, {1, 2, 5} is the only exact hitting set, as the following argument 
demonstrates: Because 2 and 7 are the only elements that hit <I>F</I>, an exact 
hitting set must contain 2 or 7, but not both. If an exact hitting set contains 
7, then it doesn't contain 1, 2, 3, 4, 5, or 6, as each of these elements are 
contained in some subset also containing 7. Then there are no more remaining 
elements, but {7} is not an exactly hitting set, as it doesn't hit <I>B</I> or 
<I>D</I>. In conclusion, there is no exact hitting set containing 7. On the 
other hand, if an exact hitting set contains 2, then it doesn't contain 3, 6, or 
7, as each of these elements are contained in some subset also containing 2. 
Because 5 is the only remaining element that hits <I>D</I>, the exact hitting 
set must contain 5. If an exact hitting set contains 5, then it doesn't contain 
4, as both hit <I>C</I>. Because 1 is the only remaining element that hits 
<I>A</I>, the exact hitting set must contain 1. Then there are no more remaining 
elements, and {1, 2, 5} is indeed an exact hitting set.</P>
<P>Although this example involves the same collection of subsets as the detailed 
exact cover example above, it is essentially a different problem. In a sense, 
the exact hitting set problem is the inverse (or transpose or converse) of the 
corresponding exact cover problem above, as the matrix representation makes 
clear:</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TH></TH>
      <TH><I>A</I></TH>
      <TH><I>B</I></TH>
      <TH><I>C</I></TH>
      <TH><I>D</I></TH>
      <TH><I>E</I></TH>
      <TH><I>F</I></TH></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TH>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red">2</SPAN></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR>
    <TR>
      <TH>3</TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD></TR>
    <TR>
      <TH>4</TH>
      <TD>1</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red">5</SPAN></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH>6</TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD></TR>
    <TR>
      <TH>7</TH>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR></TBODY></TABLE></DD></DL>
<H3><SPAN class=editsection>[<A title="Edit section: Dual example" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=12">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Dual_example>Dual example</SPAN></H3>
<P>But there is another exact hitting set problem that is essentially the same 
as the <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Detailed_example">detailed exact 
cover example</A> above, in which numbered elements become subsets and lettered 
subsets become elements, effectively inverting the relation between subsets and 
element.</P>
<P>For example, as the subset <I>B</I> contains the elements 1 and 4 in the 
exact cover problem, the subsets <I>I</I> and <I>IV</I> contain the element 
<I>b</I> in the dual exact hitting set problem.</P>
<P>In particular, let <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
= {<I>I</I>, <I>II</I>, <I>III</I>, <I>IV</I>, <I>V</I>, <I>VI</I>, <I>VII</I>} 
be a collection of subsets of a set <I>X</I> = {<I>a</I>, <I>b</I>, <I>c</I>, 
<I>d</I>, <I>e</I>, <I>f</I>} such that:</P>
<UL>
  <LI><I>I</I> = {<I>a</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>b</I></SPAN>} 
  <LI><I>II</I> = {<I>e</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>f</I></SPAN>} 
  <LI><I>III</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>d</I></SPAN>, 
  <I>e</I>} 
  <LI><I>IV</I> = {<I>a</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>b</I></SPAN>, <I>c</I>} 
  <LI><I>V</I> = {<I>c</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>d</I></SPAN>} 
  <LI><I>VI</I> = {<SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>d</I></SPAN>, 
  <I>e</I>} 
  <LI><I>VII</I> = {<I>a</I>, <I>c</I>, <I>e</I>, <SPAN 
  style="FONT-WEIGHT: bold; COLOR: red"><I>f</I></SPAN>} </LI></UL>
<P>Then <I>X*</I> = {<I>b</I>, <I>d</I>, <I>f</I>} is an exact hitting set, 
since each subset in <IMG class=tex alt=\mathcal{S} 
src="Exact cover - Wikipedia, the free encyclopedia.files/3791545a70a6e462451c97ad925d43a4.png"> 
contains (is hit by) exactly one element in <I>X*</I>, as the highlighting makes 
clear.</P>
<P>The exact hitting set <I>X*</I> = {<I>b</I>, <I>d</I>, <I>f</I>} here is 
essentially the same as the exact cover <IMG class=tex alt=\mathcal{S}^* 
src="Exact cover - Wikipedia, the free encyclopedia.files/a4c9601f599d2f9c9889246bad96f68b.png"> 
= {<I>B</I>, <I>D</I>, <I>F</I>} above, as the matrix representation makes 
clear:</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TH></TH>
      <TH><I>I</I></TH>
      <TH><I>II</I></TH>
      <TH><I>III</I></TH>
      <TH><I>IV</I></TH>
      <TH><I>V</I></TH>
      <TH><I>VI</I></TH>
      <TH><I>VII</I></TH></TR>
    <TR>
      <TH><I>a</I></TH>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>b</I></SPAN></TH>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>c</I></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>d</I></SPAN></TH>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD></TR>
    <TR>
      <TH><I>e</I></TH>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>1</TD>
      <TD>1</TD></TR>
    <TR>
      <TH><SPAN style="FONT-WEIGHT: bold; COLOR: red"><I>f</I></SPAN></TH>
      <TD>0</TD>
      <TD><SPAN style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD>0</TD>
      <TD><SPAN 
  style="FONT-WEIGHT: bold; COLOR: red">1</SPAN></TD></TR></TBODY></TABLE></DD></DL>
<H2><SPAN class=editsection>[<A title="Edit section: Finding solutions" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=13">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Finding_solutions>Finding solutions</SPAN></H2>
<P><A title="Knuth's Algorithm X" 
href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Knuth's Algorithm X</A> 
is a <A title="Recursion (computer science)" 
href="http://en.wikipedia.org/wiki/Recursion_(computer_science)">recursive</A>, 
<A class=mw-redirect title=Nondeterministic 
href="http://en.wikipedia.org/wiki/Nondeterministic">nondeterministic</A>, <A 
class=mw-redirect title=Depth-first 
href="http://en.wikipedia.org/wiki/Depth-first">depth-first</A>, <A 
title=Backtracking 
href="http://en.wikipedia.org/wiki/Backtracking">backtracking</A> <A 
title=Algorithm href="http://en.wikipedia.org/wiki/Algorithm">algorithm</A> that 
finds all solutions to the exact cover problem.</P>
<P><A title="Dancing Links" 
href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A>, commonly 
known as DLX, is the technique suggested by <A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</A> to efficiently 
implement his Algorithm X on a computer. Dancing Links uses the matrix 
representation of the problem. Dancing Links implements the matrix as a series 
of <A class=mw-redirect title="Linked lists" 
href="http://en.wikipedia.org/wiki/Linked_lists#Doubly-linked_list">doubly-linked 
lists</A> of the 1s of the matrix: each 1 element has a link to the next 1 
above, below, to the left, and to the right of itself.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Generalizations" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=14">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Generalizations>Generalizations</SPAN></H2>
<P>In a standard exact cover problem, each constraint must be satisfied exactly 
once. It is a simple generalization to relax this requirement slightly and allow 
for the possibility that some "primary" constraints must be satisfied by 
<I>exactly one</I> selection but other "secondary" constraints can be satisfied 
by <I>at most one</I> selection.</P>
<P>As Knuth explains, a generalized exact cover problem can be converted to an 
equivalent exact cover problem by simply appending one row for each secondary 
column, containing a single 1 in that column.<SUP class=reference 
id=cite_ref-3><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-3"><SPAN>[</SPAN>4<SPAN>]</SPAN></A></SUP> 
If in a particular candidate solution a particular secondary column is 
satisfied, then the added row isn't needed. But if the secondary column isn't 
satisfied, as is allowed in the generalized problem but not the standard 
problem, then the added row can be selected to ensure the column is 
satisfied.</P>
<P>But Knuth goes on to explain that it is better working with the generalized 
problem directly, because the generalized algorithm is simpler and faster: A 
simple change to his Algorithm X allows secondary columns to be handled 
directly.</P>
<P>The <A class=mw-redirect title="N queens problem" 
href="http://en.wikipedia.org/wiki/N_queens_problem">N queens problem</A> is an 
example of a generalized exact cover problem, as the constraints corresponding 
to the diagonals of the chessboard need not be satisfied.</P>
<H2><SPAN class=editsection>[<A title="Edit section: Noteworthy examples" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=15">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Noteworthy_examples>Noteworthy examples</SPAN></H2>
<P>Due to its NP-completeness, any problem in NP can be <A 
title="Reduction (complexity)" 
href="http://en.wikipedia.org/wiki/Reduction_(complexity)">reduced</A> to exact 
cover problems, which then can be solved with techniques such as Dancing Links. 
However, for some well known problems, the reduction is particularly direct. For 
instance, the problem of tiling a board with <A class=mw-redirect 
title=Pentominoes 
href="http://en.wikipedia.org/wiki/Pentominoes">pentominoes</A>, and solving <A 
title=Sudoku href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</A> can both be 
viewed as exact cover problems.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Pentomino tiling" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=16">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Pentomino_tiling>Pentomino tiling</SPAN></H3>
<DIV class="rellink relarticle mainarticle">Main article: <A title=Pentomino 
href="http://en.wikipedia.org/wiki/Pentomino">Pentomino</A></DIV>
<P>The problem of tiling a 60-square board with 12 <A class=mw-redirect 
title=Pentominoes 
href="http://en.wikipedia.org/wiki/Pentominoes">pentominoes</A> is an example of 
an exact cover problem, as <A title="Donald Knuth" 
href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald Knuth</A> explains in 
his paper "Dancing links."<SUP class=reference id=cite_ref-knuth_4-0><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-knuth-4"><SPAN>[</SPAN>5<SPAN>]</SPAN></A></SUP></P>
<P>For example, consider the problem of tiling with pentominoes an 8×8 
chessboard with the 4 central squares removed:</P>
<DL>
  <DD>
  <TABLE cellSpacing=0 cellPadding=5 border=1>
    <TBODY>
    <TR>
      <TD>11</TD>
      <TD>12</TD>
      <TD>13</TD>
      <TD>14</TD>
      <TD>15</TD>
      <TD>16</TD>
      <TD>17</TD>
      <TD>18</TD></TR>
    <TR>
      <TD>21</TD>
      <TD>22</TD>
      <TD>23</TD>
      <TD>24</TD>
      <TD>25</TD>
      <TD>26</TD>
      <TD>27</TD>
      <TD>28</TD></TR>
    <TR>
      <TD>31</TD>
      <TD>32</TD>
      <TD>33</TD>
      <TD>34</TD>
      <TD>35</TD>
      <TD>36</TD>
      <TD>37</TD>
      <TD>38</TD></TR>
    <TR>
      <TD>41</TD>
      <TD>42</TD>
      <TD>43</TD>
      <TD></TD>
      <TD></TD>
      <TD>46</TD>
      <TD>47</TD>
      <TD>48</TD></TR>
    <TR>
      <TD>51</TD>
      <TD>52</TD>
      <TD>53</TD>
      <TD></TD>
      <TD></TD>
      <TD>56</TD>
      <TD>57</TD>
      <TD>58</TD></TR>
    <TR>
      <TD>61</TD>
      <TD>62</TD>
      <TD>63</TD>
      <TD>64</TD>
      <TD>65</TD>
      <TD>66</TD>
      <TD>67</TD>
      <TD>68</TD></TR>
    <TR>
      <TD>71</TD>
      <TD>72</TD>
      <TD>73</TD>
      <TD>74</TD>
      <TD>75</TD>
      <TD>76</TD>
      <TD>77</TD>
      <TD>78</TD></TR>
    <TR>
      <TD>81</TD>
      <TD>82</TD>
      <TD>83</TD>
      <TD>84</TD>
      <TD>85</TD>
      <TD>86</TD>
      <TD>87</TD>
      <TD>88</TD></TR></TBODY></TABLE></DD></DL>
<P>The problem involves two kinds of constraints:</P>
<DL>
  <DD><B>Pentomino:</B> For each of the 12 pentominoes, there is the constraint 
  that it must be placed exactly once. Name these constraints after the 
  corresponding pentominoes: F I L P N T U V W X Y Z.<SUP class=reference 
  id=cite_ref-5><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-5"><SPAN>[</SPAN>6<SPAN>]</SPAN></A></SUP> 

  <DD><B>Square:</B> For each of the 60 squares, there is the constraint that it 
  must be covered by a pentomino exactly once. Name these constraints after the 
  corresponding squares in the board: <I>ij</I>, where <I>i</I> is the rank and 
  <I>j</I> is the file. </DD></DL>
<P>Thus there are 12+60 = 72 constraints in all.</P>
<P>As both kinds of constraints are "exactly-one" constraints, the problem is an 
exact cover problem.</P>
<P>The problem involves many choices, one for each way to place a pentomino on 
the board. It is convenient to consider each choice as a sets of 6 constraints: 
1 constraint for the pentomino being placed and 5 constraints for the five 
squares where it is placed.</P>
<P>In the case of an 8×8 chessboard with the 4 central squares removed, there 
are 1568 such choices, for example:</P>
<UL>
  <LI>{F, 12, 13, 21, 22, 32} 
  <LI>{F, 13, 14, 22, 23, 33} 
  <LI>… 
  <LI>{I, 11, 12, 13, 14, 15} 
  <LI>{I, 12, 13, 14, 15, 16} 
  <LI>… 
  <LI>{L, 11, 21, 31, 41, 42} 
  <LI>{L, 12, 22, 32, 42, 43} 
  <LI>… </LI></UL>
<P>One of many solutions of this exact cover problem is the following set of 12 
choices:</P>
<UL>
  <LI>{I, 11, 12, 13, 14, 15} 
  <LI>{N, 16, 26, 27, 37, 47} 
  <LI>{L, 17, 18, 28, 38, 48} 
  <LI>{U, 21, 22, 31, 41, 42} 
  <LI>{X, 23, 32, 33, 34, 43} 
  <LI>{W, 24, 25, 35, 36, 46} 
  <LI>{P, 51, 52, 53, 62, 63} 
  <LI>{F, 56, 64, 65, 66, 75} 
  <LI>{Z, 57, 58, 67, 76, 77} 
  <LI>{T, 61, 71, 72, 73, 81} 
  <LI>{V, 68, 78, 86, 87, 88} 
  <LI>{Y, 74, 82, 83, 84, 85} </LI></UL>
<P>This set of choices corresponds to the following solution to the pentomino 
tiling problem:</P>
<DIV class=floatnone><A class=image 
href="http://en.wikipedia.org/wiki/File:Pentomino_Puzzle_Solution_8x8_Minus_Center.svg"><IMG 
height=252 alt="Pentomino Puzzle Solution 8x8 Minus Center.svg" 
src="Exact cover - Wikipedia, the free encyclopedia.files/300px-Pentomino_Puzzle_Solution_8x8_Minus_Center.svg.png" 
width=300></A></DIV>
<P>A pentomino tiling problem is more naturally viewed as an exact cover problem 
than an exact hitting set problem, because it is more natural to view each 
choice as a set of constraints than each constraint as a set of choices. Each 
choice is related to just 6 constraints, which are easy to enumerate. On the 
other hand, each constraint is related to many choices, which are harder to 
enumerate.</P>
<P>Whether viewed as an exact cover problem or an exact hitting set problem, the 
matrix representation is the same, having 1568 rows corresponding to choices and 
72 columns corresponding to constraints. Each row contains a single 1 in the 
column identifying the pentomino and five 1s in the columns identifying the 
squares covered by the pentomino. Using the matrix, a computer can find all 
solutions relatively quickly, for example, using <A title="Dancing Links" 
href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A>.</P>
<P>See also <A class="external text" href="http://yucs.org/~gnivasch/pentomino/" 
rel=nofollow>Solving Pentomino Puzzles with Backtracking</A>.</P>
<H3><SPAN class=editsection>[<A title="Edit section: Sudoku" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=17">edit</A>]</SPAN> 
<SPAN class=mw-headline id=Sudoku>Sudoku</SPAN></H3>
<DIV class="rellink relarticle mainarticle">Main article: <A title=Sudoku 
href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</A></DIV>
<P>The problem in <A title=Sudoku 
href="http://en.wikipedia.org/wiki/Sudoku">Sudoku</A> is to assign numbers (or 
digits, values, symbols) to cells (or squares) in a grid so as to satisfy 
certain constraints.</P>
<P>In the standard 9×9 Sudoku variant, there are four kinds of constraints:</P>
<DL>
  <DD><B>Row-Column:</B> Each intersection of a row and column, i.e, each cell, 
  must contain exactly one number. 
  <DD><B>Row-Number:</B> Each row must contain each number exactly once 
  <DD><B>Column-Number:</B> Each column must contain each number exactly once. 
  <DD><B>Box-Number:</B> Each box must contain each number exactly once. 
</DD></DL>
<P>While the first constraint might seem trivial, it is nevertheless needed to 
ensure there is only one number per cell.</P>
<P>Solving Sudoku is an exact cover problem.</P>
<P>More precisely, solving Sudoku is an exact <A class=mw-redirect 
title="Hitting set" href="http://en.wikipedia.org/wiki/Hitting_set">hitting 
set</A> problem, which is equivalent to an exact cover problem (as in <A 
href="http://en.wikipedia.org/wiki/Exact_cover#Example_5">Example 5</A> above), 
when viewed as a problem to select possibilities such that each constraint set 
contains (i.e., is hit by) exactly one selected possibility. In the notation 
above for the (generalized) exact cover problem, <I>X</I> is the set of 
possibilities, <I>Y</I> is a set of constraint sets, and <I>R</I> is the binary 
relation "is contained in."</P>
<P>Each possible assignment of a particular number to a particular cell is a 
<B>possibility</B> (or candidate). When Sudoku is played with pencil and paper, 
possibilities are often called pencil marks.</P>
<P>In the standard 9×9 Sudoku variant, in which each of 9×9 cells is assigned 
one of 9 numbers, there are 9×9×9=729 possibilities. Using obvious notation for 
rows, columns and numbers, the possibilities can be labeled</P>
<DL>
  <DD>R1C1#1, R1C1#2, …, R9C9#9. </DD></DL>
<P>The fact that each kind of constraint involves exactly one of something is 
what makes Sudoku an exact hitting set problem. The constraints can be 
represented by <B>constraint sets</B>. The problem is to select possibilities 
such that each constraint set contains (i.e., is hit by) exactly one selected 
possibility.</P>
<P>In the standard 9×9 Sudoku variant, there are four kinds of constraints sets 
corresponding to the four kinds of constraints:</P>
<DL>
  <DD><B>Row-Column:</B> A row-column constraint set contains all the 
  possibilities for the intersection of a particular row and column, i.e., for a 
  cell. For example, the constraint set for row 1 and column 1, which can be 
  labeled R1C1, contains the 9 possibilities for row 1 and column 1 but 
  different numbers: 
  <DL>
    <DD>R1C1 = { R1C1#1, R1C1#2, R1C1#3, R1C1#4, R1C1#5, R1C1#6, R1C1#7, R1C1#8, 
    R1C1#9 }. </DD></DL></DD></DL>
<DL>
  <DD><B>Row-Number:</B> A row-number constraint set contains all the 
  possibilities for a particular row and number. For example, the constraint set 
  for row 1 and number 1, which can be labeled R1#1, contains the 9 
  possibilities for row 1 and number 1 but different columns: 
  <DL>
    <DD>R1#1 = { R1C1#1, R1C2#1, R1C3#1, R1C4#1, R1C5#1, R1C6#1, R1C7#1, R1C8#1, 
    R1C9#1 }. </DD></DL></DD></DL>
<DL>
  <DD><B>Column-Number:</B> A column-number constraint set contains all the 
  possibilities for a particular column and number. For example, the constraint 
  set for column 1 and number 1, which can be labeled C1#1, contains the 9 
  possibilities for column 1 and number 1 but different rows: 
  <DL>
    <DD>C1#1 = { R1C1#1, R2C1#1, R3C1#1, R4C1#1, R5C1#1, R6C1#1, R7C1#1, R8C1#1, 
    R9C1#1 }. </DD></DL></DD></DL>
<DL>
  <DD><B>Box-Number:</B> A box-number constraint set contains all the 
  possibilities for a particular box and number. For example, the constraint set 
  for box 1 (in the upper lefthand corner) and number 1, which can be labeled 
  B1#1, contains the 9 possibilities for the cells in box 1 and number 1: 
  <DL>
    <DD>B1#1 = { R1C1#1, R1C2#1, R1C3#1, R2C1#1, R2C2#1, R2C3#1, R3C1#1, R3C2#1, 
    R3C3#1 }. </DD></DL></DD></DL>
<P>Since there are 9 rows, 9 columns, 9 boxes and 9 numbers, there are 9×9=81 
row-column constraint sets, 9×9=81 row-number constraint sets, 9×9=81 
column-number constraint sets, and 9×9=81 box-number constraint sets: 
81+81+81+81=324 constraint sets in all.</P>
<P>In brief, the standard 9×9 Sudoku variant is an exact hitting set problem 
with 729 possibilities and 324 constraint sets. Thus the problem can be 
represented by a 729×324 matrix.</P>
<P>Although it is difficult to present the entire 729×324 matrix, the general 
nature of the matrix can be seen from several snapshots:</P>
<TABLE cellSpacing=30>
  <TBODY>
  <TR vAlign=top>
    <TD>
      <TABLE style="TEXT-ALIGN: center" cellSpacing=0 cellPadding=5 border=1>
        <CAPTION><B>Row-Column Constraints</B></CAPTION>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>R1<BR>C1</TH>
          <TH>R1<BR>C2</TH>
          <TH>…</TH></TR>
        <TR>
          <TH>R1C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#2</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#3</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#4</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#5</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#6</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#7</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#8</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#9</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#1</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#3</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#4</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#5</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#6</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#7</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#8</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#9</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR></TBODY></TABLE></TD>
    <TD>
      <TABLE style="TEXT-ALIGN: center" cellSpacing=0 cellPadding=5 border=1>
        <CAPTION><B>Row-Number Constraints</B></CAPTION>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>R1<BR>#1</TH>
          <TH>R1<BR>#2</TH>
          <TH>…</TH></TR>
        <TR>
          <TH>R1C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C3#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C3#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C4#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C4#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C5#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C5#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C6#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C6#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C7#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C7#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C8#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C8#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C9#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C9#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR></TBODY></TABLE></TD>
    <TD>
      <TABLE style="TEXT-ALIGN: center" cellSpacing=0 cellPadding=5 border=1>
        <CAPTION><B>Column-Number Constraints</B></CAPTION>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>C1<BR>#1</TH>
          <TH>C1<BR>#2</TH>
          <TH>…</TH></TR>
        <TR>
          <TH>R1C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R4C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R4C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R5C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R5C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R6C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R6C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R7C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R7C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R8C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R8C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R9C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R9C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR></TBODY></TABLE></TD>
    <TD>
      <TABLE style="TEXT-ALIGN: center" cellSpacing=0 cellPadding=5 border=1>
        <CAPTION><B>Box-Number Constraints</B></CAPTION>
        <TBODY>
        <TR>
          <TH></TH>
          <TH>B1<BR>#1</TH>
          <TH>B1<BR>#2</TH>
          <TH>…</TH></TR>
        <TR>
          <TH>R1C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C2#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C3#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R1C3#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C2#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C2#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C3#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R2C3#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C1#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C1#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C2#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C2#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C3#1</TH>
          <TD>1</TD>
          <TD>0</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>R3C3#2</TH>
          <TD>0</TD>
          <TD>1</TD>
          <TD>…</TD></TR>
        <TR>
          <TH>…</TH>
          <TD>…</TD>
          <TD>…</TD>
          <TD>…</TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<P>The <A class="external text" 
href="http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm" 
rel=nofollow>complete 729×324 matrix</A> is available from Bob Hanson.</P>
<P>Note that the set of possibilities R<I>x</I>C<I>y</I>#<I>z</I> can be 
arranged as a 9×9×9 cube in a 3-dimensional space with coordinates <I>x</I>, 
<I>y</I>, and <I>z</I>. Then each row R<I>x</I>, column C<I>y</I>, or number 
#<I>z</I> is a 9×9×1 "slice" of possibilities; each box B<I>w</I> is a 9x3×3 
"tube" of possibilities; each row-column constraint set R<I>x</I>C<I>y</I>, 
row-number constraint set R<I>x</I>#<I>z</I>, or column-number constraint set 
C<I>y</I>#<I>z</I> is a 9x1×1 "strip" of possibilities; each box-number 
constraint set B<I>w</I>#<I>z</I> is a 3x3×1 "square" of possibilities; and each 
possibility R<I>x</I>C<I>y</I>#<I>z</I> is a 1x1×1 "cubie" consisting of a 
single possibility. Moreover, each constraint set or possibility is the <A 
title="Intersection (set theory)" 
href="http://en.wikipedia.org/wiki/Intersection_(set_theory)">intersection</A> 
of the component sets. For example, R1C2#3 = R1 ∩ C2 ∩ #3, where ∩ denotes set 
intersection.</P>
<P>Although other Sudoku variations have different numbers of rows, columns, 
numbers and/or different kinds of constraints, they all involve possibilities 
and constraint sets, and thus can be seen as exact hitting set problems.</P>
<H3><SPAN class=editsection>[<A title="Edit section: N queens problem" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=18">edit</A>]</SPAN> 
<SPAN class=mw-headline id=N_queens_problem>N queens problem</SPAN></H3>
<DIV class="rellink relarticle mainarticle">Main article: <A class=mw-redirect 
title="N queens problem" href="http://en.wikipedia.org/wiki/N_queens_problem">N 
queens problem</A></DIV>
<TABLE class="metadata plainlinks ambox mbox-small-left ambox-notice">
  <TBODY>
  <TR>
    <TD class=mbox-image><A class=image 
      href="http://en.wikipedia.org/wiki/File:Wiki_letter_w.svg"><IMG height=20 
      alt="Wiki letter w.svg" 
      src="Exact cover - Wikipedia, the free encyclopedia.files/20px-Wiki_letter_w.svg.png" 
      width=20></A></TD>
    <TD class=mbox-text>This section requires <A class="external text" 
      href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit" 
      rel=nofollow>expansion</A>.</TD></TR></TBODY></TABLE>
<P>The <A class=mw-redirect title="N queens problem" 
href="http://en.wikipedia.org/wiki/N_queens_problem">N queens problem</A> is an 
example of a generalized exact cover problem.<SUP class=reference 
id=cite_ref-knuth_4-1><A 
href="http://en.wikipedia.org/wiki/Exact_cover#cite_note-knuth-4"><SPAN>[</SPAN>5<SPAN>]</SPAN></A></SUP> 
The problem involves four kinds of constraints:</P>
<DL>
  <DD><B>Rank:</B> For each of the N ranks, there must be exactly one queen. 
  <DD><B>File:</B> For each of the N files, there must be exactly one queen. 
  <DD><B>Diagonals:</B> For each of the 2N - 1 diagonals, there must be at most 
  one queen. 
  <DD><B>Reverse diagonals:</B> For each of the 2N - 1 reverse diagonals, there 
  must be at most one queen. </DD></DL>
<P>Note that the 2N rank and file constraints form the primary constraints, 
while the 4N - 2 diagonal and reverse diagonals form the secondary constraints. 
Further, because the each of first and last diagonal and reverse diagonals 
involve only one square on the chessboard, these can be omitted and thus we can 
reduce the number of secondary constraints to 4N - 6. The matrix for the N 
queens problem then have N² rows and 6N - 6 columns, each row for a possible 
queen placement on each square on the chessboard, and each column for each 
constraint.</P>
<H2><SPAN class=editsection>[<A title="Edit section: See also" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=19">edit</A>]</SPAN> 
<SPAN class=mw-headline id=See_also>See also</SPAN></H2>
<UL>
  <LI><A title="Constraint satisfaction problem" 
  href="http://en.wikipedia.org/wiki/Constraint_satisfaction_problem">Constraint 
  satisfaction problem</A> 
  <LI><A title="Dancing Links" 
  href="http://en.wikipedia.org/wiki/Dancing_Links">Dancing Links</A> 
  <LI><A title="Difference map algorithm" 
  href="http://en.wikipedia.org/wiki/Difference_map_algorithm">Difference map 
  algorithm</A> 
  <LI><A class=mw-redirect title="Hitting set" 
  href="http://en.wikipedia.org/wiki/Hitting_set">Hitting set</A> 
  <LI><A title="Karp's 21 NP-complete problems" 
  href="http://en.wikipedia.org/wiki/Karp's_21_NP-complete_problems">Karp's 21 
  NP-complete problems</A> 
  <LI><A title="Knuth's Algorithm X" 
  href="http://en.wikipedia.org/wiki/Knuth's_Algorithm_X">Knuth's Algorithm 
  X</A> 
  <LI><A title="List of NP-complete problems" 
  href="http://en.wikipedia.org/wiki/List_of_NP-complete_problems">List of 
  NP-complete problems</A> 
  <LI><A class=mw-redirect title="Perfect matching" 
  href="http://en.wikipedia.org/wiki/Perfect_matching">Perfect matching</A> and 
  <A title="3-dimensional matching" 
  href="http://en.wikipedia.org/wiki/3-dimensional_matching">3-dimensional 
  matching</A> are special cases of the exact cover problem </LI></UL>
<H2><SPAN class=editsection>[<A title="Edit section: References" 
href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit&amp;section=20">edit</A>]</SPAN> 
<SPAN class=mw-headline id=References>References</SPAN></H2>
<DIV class=references-small>
<OL class=references>
  <LI id=cite_note-0><B><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-0">^</A></B> <SPAN 
  class="citation book"><A title="Michael Garey" 
  href="http://en.wikipedia.org/wiki/Michael_Garey">M.R. Garey</A>; <A 
  title="David S. Johnson" 
  href="http://en.wikipedia.org/wiki/David_S._Johnson">D.S. Johnson</A> (1979). 
  <I><A 
  title="Computers and Intractability: A Guide to the Theory of NP-Completeness" 
  href="http://en.wikipedia.org/wiki/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness">Computers 
  and Intractability: A Guide to the Theory of NP-Completeness</A></I>. New 
  York: W.H. Freeman. <A title="International Standard Book Number" 
  href="http://en.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</A> 
  <A title=Special:BookSources/0-7167-1045-5 
  href="http://en.wikipedia.org/wiki/Special:BookSources/0-7167-1045-5">0-7167-1045-5</A>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=%5B%5BComputers+and+Intractability%3A+A+Guide+to+the+Theory+of+NP-Completeness%5D%5D&amp;rft.aulast=M.R.+Garey&amp;rft.au=M.R.+Garey&amp;rft.au=%5B%5BDavid+S.+Johnson%7CD.S.+Johnson%5D%5D&amp;rft.date=1979&amp;rft.place=New+York&amp;rft.pub=W.H.+Freeman&amp;rft.isbn=0-7167-1045-5&amp;rfr_id=info:sid/en.wikipedia.org:Exact_cover><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> This book is a classic, developing 
  the theory, then cataloguing <I>many</I> NP-Complete problems. 
  <LI id=cite_note-1><B><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-1">^</A></B> <SPAN 
  class="citation book"><A title="Richard Karp" 
  href="http://en.wikipedia.org/wiki/Richard_Karp">Richard M. Karp</A> (1972). 
  "<A class="external text" 
  href="http://www.cs.berkeley.edu/~luca/cs172/karp.pdf" 
  rel=nofollow>Reducibility among combinatorial problems</A>". in R.E. Miller 
  and J.W. Thatcher (editors). <I>Proc. of a Symp. on the Complexity of Computer 
  Computations</I>. Complexity of Computer Computations. New York: Plenum. 
  pp.&nbsp;85–103. <A class="internal mw-magiclink-isbn" 
  href="http://en.wikipedia.org/wiki/Special:BookSources/0306307073">ISBN 
  0-3063-0707-3</A>.</SPAN><SPAN class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=bookitem&amp;rft.btitle=%5Bhttp%3A%2F%2Fwww.cs.berkeley.edu%2F%7Eluca%2Fcs172%2Fkarp.pdf+Reducibility+among+combinatorial+problems%5D&amp;rft.atitle=Proc.+of+a+Symp.+on+the+Complexity+of+Computer+Computations&amp;rft.aulast=Richard+M.+Karp&amp;rft.au=Richard+M.+Karp&amp;rft.date=1972&amp;rft.series=Complexity+of+Computer+Computations&amp;rft.pages=pp.%26nbsp%3B85%E2%80%93103&amp;rft.place=New+York&amp;rft.pub=Plenum&amp;rfr_id=info:sid/en.wikipedia.org:Exact_cover><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI id=cite_note-2><B><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-2">^</A></B> <A 
  title="Donald Knuth" href="http://en.wikipedia.org/wiki/Donald_Knuth">Donald 
  Knuth</A> in his paper "Dancing Links" gives this example, as equation (3), 
  only with the rows reordered. 
  <LI id=cite_note-3><B><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-3">^</A></B> Donald 
  Knuth explains this simple generalization in his paper "Dancing Links," in 
  particular, in explaining the tetrastick and <A class=mw-redirect 
  title="N queens problem" 
  href="http://en.wikipedia.org/wiki/N_queens_problem">N queens</A> problems. 
  <LI id=cite_note-knuth-4>^ <A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-knuth_4-0"><SUP><I><B>a</B></I></SUP></A> 
  <A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-knuth_4-1"><SUP><I><B>b</B></I></SUP></A> 
  <SPAN class="citation Journal"><A title="Donald Knuth" 
  href="http://en.wikipedia.org/wiki/Donald_Knuth">Knuth, Donald</A> (2000) (<A 
  class=mw-redirect title=PDF href="http://en.wikipedia.org/wiki/PDF">PDF</A>). 
  <A class="external text" href="http://lanl.arxiv.org/pdf/cs/0011047" 
  rel=nofollow><I>Dancing links</I></A><SPAN class=printonly>. <A 
  class="external free" href="http://lanl.arxiv.org/pdf/cs/0011047" 
  rel=nofollow>http://lanl.arxiv.org/pdf/cs/0011047</A></SPAN><SPAN 
  class=reference-accessdate>. Retrieved 2008-05-31</SPAN>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Dancing+links&amp;rft.aulast=%5B%5BDonald+Knuth%7CKnuth%2C+Donald%5D%5D&amp;rft.au=%5B%5BDonald+Knuth%7CKnuth%2C+Donald%5D%5D&amp;rft.date=2000&amp;rft_id=http%3A%2F%2Flanl.arxiv.org%2Fpdf%2Fcs%2F0011047&amp;rfr_id=info:sid/en.wikipedia.org:Exact_cover><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> 
  <LI id=cite_note-5><B><A 
  href="http://en.wikipedia.org/wiki/Exact_cover#cite_ref-5">^</A></B> <SPAN 
  class="citation book"><A title="Solomon W. Golomb" 
  href="http://en.wikipedia.org/wiki/Solomon_W._Golomb">Golomb, Solomon W.</A>; 
  Warren Lushbaugh (1994). <I>Polyominoes: Puzzles, Patterns, Problems, and 
  Packings</I> (2nd ed. ed.). Princeton, New Jersey: Princeton University Press. 
  p.&nbsp;7. <A title="International Standard Book Number" 
  href="http://en.wikipedia.org/wiki/International_Standard_Book_Number">ISBN</A> 
  <A title=Special:BookSources/0691024448 
  href="http://en.wikipedia.org/wiki/Special:BookSources/0691024448">0691024448</A>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=book&amp;rft.btitle=Polyominoes%3A+Puzzles%2C+Patterns%2C+Problems%2C+and+Packings&amp;rft.aulast=Golomb&amp;rft.aufirst=Solomon+W.&amp;rft.au=Golomb%2C%26%2332%3BSolomon+W.&amp;rft.au=Warren+Lushbaugh&amp;rft.date=1994&amp;rft.pages=p.%26nbsp%3B7&amp;rft.edition=2nd+ed.&amp;rft.place=Princeton%2C+New+Jersey&amp;rft.pub=Princeton+University+Press&amp;rft.isbn=0691024448&amp;rfr_id=info:sid/en.wikipedia.org:Exact_cover><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> </LI></OL></DIV>
<UL>
  <LI><SPAN class="citation web">Dahlke, K. "<A class="external text" 
  href="http://www.mathreference.com/lan-cx-np,excov.html" rel=nofollow>Exact 
  cover</A>". <I>Math Reference Project</I><SPAN class=printonly>. <A 
  class="external free" href="http://www.mathreference.com/lan-cx-np,excov.html" 
  rel=nofollow>http://www.mathreference.com/lan-cx-np,excov.html</A></SPAN><SPAN 
  class=reference-accessdate>. Retrieved 2008-06-21</SPAN>.</SPAN><SPAN 
  class=Z3988 
  title=ctx_ver=Z39.88-2004&amp;rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&amp;rft.genre=bookitem&amp;rft.btitle=Exact+cover&amp;rft.atitle=Math+Reference+Project&amp;rft.aulast=Dahlke&amp;rft.aufirst=K&amp;rft.au=Dahlke%2C%26%2332%3BK&amp;rft_id=http%3A%2F%2Fwww.mathreference.com%2Flan-cx-np%2Cexcov.html&amp;rfr_id=info:sid/en.wikipedia.org:Exact_cover><SPAN 
  style="DISPLAY: none">&nbsp;</SPAN></SPAN> </LI></UL><!-- 
NewPP limit report
Preprocessor node count: 3777/1000000
Post-expand include size: 22287/2048000 bytes
Template argument size: 7304/2048000 bytes
Expensive parser function count: 1/500
--><!-- Saved in parser cache with key enwiki:pcache:idhash:2828651-0!1!0!default!!en!2 and timestamp 20091216151641 -->
<DIV class=printfooter>Retrieved from "<A 
href="http://en.wikipedia.org/wiki/Exact_cover">http://en.wikipedia.org/wiki/Exact_cover</A>"</DIV>
<DIV class=catlinks id=catlinks>
<DIV id=mw-normal-catlinks><A title=Special:Categories 
href="http://en.wikipedia.org/wiki/Special:Categories">Categories</A>: <SPAN 
dir=ltr><A title="Category:Theoretical computer science" 
href="http://en.wikipedia.org/wiki/Category:Theoretical_computer_science">Theoretical 
computer science</A></SPAN> | <SPAN dir=ltr><A 
title="Category:NP-complete problems" 
href="http://en.wikipedia.org/wiki/Category:NP-complete_problems">NP-complete 
problems</A></SPAN></DIV>
<DIV class=mw-hidden-cats-hidden id=mw-hidden-catlinks>Hidden categories: <SPAN 
dir=ltr><A title="Category:Articles to be expanded from July 2008" 
href="http://en.wikipedia.org/wiki/Category:Articles_to_be_expanded_from_July_2008">Articles 
to be expanded from July 2008</A></SPAN> | <SPAN dir=ltr><A 
title="Category:All articles to be expanded" 
href="http://en.wikipedia.org/wiki/Category:All_articles_to_be_expanded">All 
articles to be expanded</A></SPAN></DIV></DIV><!-- end content -->
<DIV class=visualClear></DIV></DIV></DIV></DIV>
<DIV id=column-one>
<DIV class=portlet id=p-cactions>
<H5>Views</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI class=selected id=ca-nstab-main><A title="View the content page [c]" 
  accessKey=c href="http://en.wikipedia.org/wiki/Exact_cover">Article</A> 
  <LI id=ca-talk><A title="Discussion about the content page [t]" accessKey=t 
  href="http://en.wikipedia.org/wiki/Talk:Exact_cover">Discussion</A> 
  <LI id=ca-edit><A 
  title="You can edit this page. &#10;Please use the preview button before saving. [e]" 
  accessKey=e 
  href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=edit">Edit 
  this page</A> 
  <LI id=ca-history><A title="Past versions of this page [h]" accessKey=h 
  href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;action=history">History</A> 
  </LI></UL></DIV></DIV>
<DIV class=portlet id=p-personal>
<H5>Personal tools</H5>
<DIV class=pBody>
<UL lang=en xml:lang="en">
  <LI id=pt-optin-try><A class=no-text-transform title="Try out new features" 
  href="http://en.wikipedia.org/w/index.php?title=Special:UsabilityInitiativeOptIn&amp;from=Exact_cover">Try 
  Beta</A> 
  <LI id=pt-login><A 
  title="You are encouraged to log in; however, it is not mandatory. [o]" 
  accessKey=o 
  href="http://en.wikipedia.org/w/index.php?title=Special:UserLogin&amp;returnto=Exact_cover">Log 
  in / create account</A> </LI></UL></DIV></DIV>
<DIV class=portlet id=p-logo><A title="Visit the main page" 
style="BACKGROUND-IMAGE: url(http://upload.wikimedia.org/wikipedia/en/b/bc/Wiki.png)" 
href="http://en.wikipedia.org/wiki/Main_Page"></A></DIV>
<SCRIPT type=text/javascript> if (window.isMSIE55) fixalpha(); </SCRIPT>

<DIV class="generated-sidebar portlet" id=p-navigation>
<H5 lang=en xml:lang="en">Navigation</H5>
<DIV class=pBody>
<UL>
  <LI id=n-mainpage-description><A title="Visit the main page [z]" accessKey=z 
  href="http://en.wikipedia.org/wiki/Main_Page">Main page</A> 
  <LI id=n-contents><A title="Guides to browsing Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Contents">Contents</A> 
  <LI id=n-featuredcontent><A title="Featured content — the best of Wikipedia" 
  href="http://en.wikipedia.org/wiki/Portal:Featured_content">Featured 
  content</A> 
  <LI id=n-currentevents><A 
  title="Find background information on current events" 
  href="http://en.wikipedia.org/wiki/Portal:Current_events">Current events</A> 
  <LI id=n-randompage><A title="Load a random article [x]" accessKey=x 
  href="http://en.wikipedia.org/wiki/Special:Random">Random article</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-search>
<H5 lang=en xml:lang="en"><LABEL for=searchInput>Search</LABEL></H5>
<DIV class=pBody id=searchBody>
<FORM id=searchform action=/w/index.php><INPUT type=hidden value=Special:Search 
name=title> <INPUT id=searchInput title="Search Wikipedia" accessKey=f 
name=search> <INPUT class=searchButton id=searchGoButton title="Go to a page with this exact name if one exists" type=submit value=Go name=go>&nbsp; 
<INPUT class=searchButton id=mw-searchButton title="Search Wikipedia for this text" type=submit value=Search name=fulltext> 
</FORM></DIV></DIV>
<DIV class="generated-sidebar portlet" id=p-interaction>
<H5 lang=en xml:lang="en">Interaction</H5>
<DIV class=pBody>
<UL>
  <LI id=n-aboutsite><A title="Find out about Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=n-portal><A 
  title="About the project, what you can do, where to find things" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Community_portal">Community 
  portal</A> 
  <LI id=n-recentchanges><A title="The list of recent changes in the wiki [r]" 
  accessKey=r href="http://en.wikipedia.org/wiki/Special:RecentChanges">Recent 
  changes</A> 
  <LI id=n-contact><A title="How to contact Wikipedia" 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</A> 

  <LI id=n-sitesupport><A title="Support us" 
  href="http://wikimediafoundation.org/wiki/Support_Wikipedia/en">Donate to 
  Wikipedia</A> 
  <LI id=n-help><A title="Guidance on how to use and edit Wikipedia" 
  href="http://en.wikipedia.org/wiki/Help:Contents">Help</A> 
</LI></UL></DIV></DIV>
<DIV class=portlet id=p-tb>
<H5 lang=en xml:lang="en">Toolbox</H5>
<DIV class=pBody>
<UL>
  <LI id=t-whatlinkshere><A 
  title="List of all English Wikipedia pages containing links to this page [j]" 
  accessKey=j 
  href="http://en.wikipedia.org/wiki/Special:WhatLinksHere/Exact_cover">What 
  links here</A> 
  <LI id=t-recentchangeslinked><A 
  title="Recent changes in pages linked from this page [k]" accessKey=k 
  href="http://en.wikipedia.org/wiki/Special:RecentChangesLinked/Exact_cover">Related 
  changes</A> 
  <LI id=t-upload><A title="Upload files [u]" accessKey=u 
  href="http://en.wikipedia.org/wiki/Wikipedia:Upload">Upload file</A> 
  <LI id=t-specialpages><A title="List of all special pages [q]" accessKey=q 
  href="http://en.wikipedia.org/wiki/Special:SpecialPages">Special pages</A> 
  <LI id=t-print><A title="Printable version of this page [p]" accessKey=p 
  href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;printable=yes" 
  rel=alternate>Printable version</A> 
  <LI id=t-permalink><A title="Permanent link to this revision of the page" 
  href="http://en.wikipedia.org/w/index.php?title=Exact_cover&amp;oldid=325680852">Permanent 
  link</A>
  <LI id=t-cite><A title="Information on how to cite this page" 
  href="http://en.wikipedia.org/w/index.php?title=Special:Cite&amp;page=Exact_cover&amp;id=325680852">Cite 
  this page</A> </LI></UL></DIV></DIV>
<DIV class=portlet id=p-lang>
<H5 lang=en xml:lang="en">Languages</H5>
<DIV class=pBody>
<UL>
  <LI class=interwiki-de><A 
  href="http://de.wikipedia.org/wiki/Problem_der_exakten_Ãberdeckung">Deutsch</A> 

  <LI class=interwiki-fr><A 
  href="http://fr.wikipedia.org/wiki/ProblÃ¨me_de_la_couverture_exacte">Français</A> 
  </LI></UL></DIV></DIV></DIV><!-- end of the left (by default at least) column -->
<DIV class=visualClear></DIV>
<DIV id=footer>
<DIV id=f-poweredbyico><A href="http://www.mediawiki.org/"><IMG height=31 
alt="Powered by MediaWiki" 
src="Exact cover - Wikipedia, the free encyclopedia.files/poweredby_mediawiki_88x31.png" 
width=88></A></DIV>
<DIV id=f-copyrightico><A href="http://wikimediafoundation.org/"><IMG height=31 
alt="Wikimedia Foundation" 
src="Exact cover - Wikipedia, the free encyclopedia.files/wikimedia-button.png" 
width=88></A></DIV>
<UL id=f-list>
  <LI id=lastmod>This page was last modified on 13 November 2009 at 20:35. 
  <LI id=copyright>Text is available under the <A 
  href="http://en.wikipedia.org/wiki/Wikipedia:Text_of_Creative_Commons_Attribution-ShareAlike_3.0_Unported_License" 
  rel=license>Creative Commons Attribution-ShareAlike License</A><A 
  style="DISPLAY: none" href="http://creativecommons.org/licenses/by-sa/3.0/" 
  rel=license></A>; additional terms may apply. See <A 
  href="http://wikimediafoundation.org/wiki/Terms_of_Use">Terms of Use</A> for 
  details.<BR>Wikipedia® is a registered trademark of the <A 
  href="http://www.wikimediafoundation.org/">Wikimedia Foundation, Inc.</A>, a 
  non-profit organization.
  <LI><A class=internal 
  href="http://en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact us</A> 
  <LI id=privacy><A title="wikimedia:Privacy policy" 
  href="http://wikimediafoundation.org/wiki/Privacy_policy">Privacy policy</A> 
  <LI id=about><A title=Wikipedia:About 
  href="http://en.wikipedia.org/wiki/Wikipedia:About">About Wikipedia</A> 
  <LI id=disclaimer><A title="Wikipedia:General disclaimer" 
  href="http://en.wikipedia.org/wiki/Wikipedia:General_disclaimer">Disclaimers</A> 
  </LI></UL></DIV></DIV>
<SCRIPT type=text/javascript>if (window.runOnloadHook) runOnloadHook();</SCRIPT>
<!-- Served by srv153 in 0.060 secs. --></BODY></HTML>
